package com.googlecode.boliang.q06.quicksort;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class QuickSort {

	public List<Integer> intQuickSort(List<Integer> intList) {
		
		List<Integer> sortedList = new LinkedList<Integer>(); 
		List<Integer> lessList = new LinkedList<Integer>(); 
		List<Integer> greaterList = new LinkedList<Integer>(); 
		
		if (intList.size() <= 1) return intList; 
		
		
		int lastValue = intList.get(intList.size()-1); 
		System.out.println("The current pivot value is :" + lastValue); 
		
		for (Iterator<Integer> intListIter = intList.listIterator(); intListIter.hasNext(); ) {
			
			int c = intListIter.next(); 
			if (c < lastValue) {
				lessList.add(c); 
			} else if(c > lastValue) {
				greaterList.add(c); 
			}

		}
		
		lessList = this.intQuickSort(lessList); 
		greaterList = this.intQuickSort(greaterList); 
		
		if (!lessList.isEmpty()) sortedList.addAll(lessList); 
		sortedList.add(lastValue); 
		if (!greaterList.isEmpty()) sortedList.addAll(greaterList); 
		
		return sortedList;
	}
}
